package com.xj.algorithm.leetcode;

/**
 * 反转链表
 */
public class L206_反转链表 {

    /**
     * 反转一个单链表。
     *
     * 示例:
     *
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     * 进阶:
     * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
     */

    public static void main(String[] args) {
        ListNode root=new ListNode(1);
        root.next=new ListNode(2);
        root.next.next=new ListNode(3);
        root.next.next.next=new ListNode(4);
        root.next.next.next.next=new ListNode(5);
        ListNode result=reverseListGood(root);
        while (result!=null){
            System.out.print(result.val+"->");
            result=result.next;
        }
        System.out.println();
    }

    //官方解法：递归。找到最后节点，然后next指向前一个节点。类似于斩断链表，重新连接
    public static ListNode reverseListOffice(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = reverseListOffice(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }

    //精彩解法：迭代。前一个节点，后一个节点，当前节点。记住这3个节点
    public static ListNode reverseListGood(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

}